package sort;

public class QuickSort {

    public static void main(String[] args) {
        int[] a = {1, 2, 2, 3, 2, 5, 4, 8};
        sort(a, 0, a.length - 1);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

    private static int partition(int[] a, int low, int high) {
        int piovt = a[low];
        int i = low;
        while (low < high) {
            // a[low+1] 跳过基准元素避免重复比较导致下标不对
            while (low < high && piovt >= a[low+1]) {
                low++;
            }
            while (low < high && piovt <= a[high]) {
                high--;
            }
            if (a[low] >= a[high]) {
                int temp = a[low];
                a[low] = a[high];
                a[high] = temp;
            }
        }
        a[i] = a[low];
        a[low] = piovt;
        return low;
    }

    public static void sort(int[] a, int low, int high) {
        if (low < high) {
            int partion = partition(a, low, high);
            sort(a, low, partion - 1);
            sort(a, partion + 1, high);
        }
    }
}
